package com.zjj.algorithm.learning.atguigu.hashtab;

import java.util.HashMap;
import java.util.Map;

/**
 * @author zjj_admin
 * @date 2022/11/20 16:25
 */
public class HashTabDemo {

    public static void main(String[] args) {

        Emp emp1 = new Emp(1, "张三1");
        Emp emp2 = new Emp(2, "张三2");
        Emp emp3 = new Emp(3, "张三3");
        Emp emp4 = new Emp(4, "张三4");
        Emp emp5 = new Emp(5, "张三5");
        Emp emp6 = new Emp(6, "张三6");
        Emp emp7 = new Emp(7, "张三7");
        Emp emp8 = new Emp(8, "张三8");
        Emp emp9 = new Emp(9, "张三9");


        //创建一个hash表，可以修改数组大小查看变化
        EmpHashTab hashTab = new EmpHashTab(4);
        hashTab.add(emp1);
        hashTab.add(emp2);
        hashTab.add(emp3);
        hashTab.add(emp4);
        hashTab.add(emp5);
        hashTab.add(emp6);
        hashTab.add(emp7);
        hashTab.add(emp8);
        hashTab.add(emp9);



        //展示hash表信息
        hashTab.list();

        Emp emp_6 = hashTab.get(6);
        System.out.println("emp_6 = " + emp_6);
        Emp emp_36 = hashTab.get(36);
        System.out.println("emp_36 = " + emp_36);

        System.out.println("============================");
        //删除hash表中的一个数据
        hashTab.del(6);
        Emp emp_6_2 = hashTab.get(6);
        System.out.println("emp_6_2 = " + emp_6_2);
        hashTab.list();

        Map<String,Object> map = new HashMap<>();
        map.put("1",1);
        Object o = map.get("1");

    }
}




/**
 * hash表
 */
class EmpHashTab {

    private EmpLinkedList[] empLinkedLists;
    /**
     * hash表中数组的大小，即有多少个链表
     */
    private int listSize;

    public EmpHashTab(int listSize) {
        this.listSize = listSize;
        empLinkedLists = new EmpLinkedList[listSize];
        for (int i = 0; i < listSize; i++) {
            empLinkedLists[i] = new EmpLinkedList();
        }
    }

    /**
     * 向hash表中添加数据
     *
     * @param emp
     */
    public void add(Emp emp) {
        int hash = getHash(emp.id);
        empLinkedLists[hash].add(emp);
    }


    /**
     * 删除hash表中的数据
     * @param id
     */
    public void del(int id){
        int hash = getHash(id);
        this.empLinkedLists[hash].delById(id);
    }

    /**
     * 遍历hash表
     */
    public void list() {
        for (int i = 0; i < this.empLinkedLists.length; i++) {
            this.empLinkedLists[i].list(i);
        }
    }

    /**
     * 获取数据的 hash 值，应该放在哪一个链表下
     *
     * @param id
     * @return
     */
    private int getHash(int id) {
        return id % this.listSize;
    }

    public Emp get(int id){
        int hash = getHash(id);
        Emp emp = this.empLinkedLists[hash].getById(id);
        return emp;
    }
}

/**
 * 链表
 */
class EmpLinkedList {

    /**
     * 头指针，默认为 null，head中不存储数据
     */
    private Emp head;

    public EmpLinkedList() {
        this.head = new Emp(Integer.MIN_VALUE, null);
    }

    /**
     * 向链表中添加数据
     *
     * @param emp
     */
    public void add(Emp emp) {
        if (this.head.next == null) {
            this.head.next = emp;
            return;
        }
        //当里面存在数据时，顺序插入
        Emp pre = head;
        Emp curr = head.next;
        while (true) {
            //当用该放在链表的尾部
            if (curr.next == null) {
                curr.next = emp;
                break;
            }
            if (curr.id > emp.id) {
                emp.next = pre.next;
                pre.next = emp;
                break;
            }
            pre = pre.next;
            curr = curr.next;
        }
    }

    /**
     * 删除链表中的指定数据
     * @param id
     */
    public void delById(int id){
        Emp pre = head;
        while (pre != null){
            if(pre.next.id == id){
                pre.next = pre.next.next;
                break;
            }
            pre = pre.next;
        }
    }

    /**
     * 遍历链表
     */
    public void list(int i) {
        if (this.head.next == null) {
            System.out.println("链表索引 " + (i + 1) + " 没有数据");
            return;
        }
        Emp curr = this.head.next;
        System.out.print("链表索引 " + (i + 1) + " 中的数据为：");
        while (curr != null) {
            System.out.printf("{id = %d, name = %s}", curr.id, curr.name);
            curr = curr.next;
        }
        System.out.println();
    }

    /**
     * 在一个链表中查找数据
     * @param id
     * @return
     */
    public Emp getById(int id){
        Emp curr = head.next;
        while (curr != null){
            if(curr.id == id){
                return curr;
            }
            curr = curr.next;
        }
        return null;
    }

}

/**
 * 雇员类
 */
class Emp {
    public int id;
    public String name;
    /**
     * 下一个节点
     */
    public Emp next;

    public Emp(int id, String name) {
        this.id = id;
        this.name = name;
    }

    @Override
    public String toString() {
        return "Emp{" +
                "id=" + id +
                ", name='" + name + '\'' +
                '}';
    }
}


